package tree.binary_tree.base;

import java.util.ArrayList;
import java.util.List;

/**
 * @author yeyangtao created at 11:21 2020/10/10
 */
public class BinarySearchTreeImpl implements BinarySearchTree {

    private static MyTree<Integer> tree = null;

    @Override
    public void insert(int value) {
        if (tree == null) {
            tree = new MyTree<>(value);
        } else {
            MyTree<Integer> curr = tree;
            while (curr != null) {
                if (curr.getValue() > value) {
                    if (curr.getLeft() == null) {
                        curr.setLeft(new MyTree<>(value));
                        return;
                    }
                    curr = curr.getLeft();
                } else {
                    if (curr.getRight() == null) {
                        curr.setRight(new MyTree<>(value));
                        return;
                    }
                    curr = curr.getRight();
                }
            }
        }
    }

    @Override
    public MyTree<?> search(int target) {
        MyTree<Integer> curr = tree;
        while (curr != null) {
            if (curr.getValue() > target)
                curr = curr.getLeft();
            else if (curr.getValue() < target)
                curr = curr.getRight();
            else
                return curr;
        }
        return null;
    }

    @Override
    public void delete(int value) {

    }

    @Override
    public List<Integer> sort() {
        List<Integer> result = new ArrayList<>();
        in(result, tree);
        return result;
    }

    private void in(List<Integer> res, MyTree<Integer> root) {
        if (tree == null) return;

        if (root.getValue() == null) return;

        in(res, root.getLeft());
        res.add(root.getValue());
        in(res, root.getRight());
    }
}
